You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate ?

এখানে প্রদত্ত সমস্যাটি হলো External Sorting (এক্সটার্নাল সর্টিং) এর একটি উদাহরণ। External Sorting হলো এমন একটি প্রক্রিয়া যেখানে সর্ট করার জন্য প্রয়োজনীয় ডেটা প্রধান মেমরি (main memory) এর চেয়ে বড় হয় এবং কিছু ডেটা সেকেন্ডারি স্টোরেজ (secondary storage) এ রাখতে হয়। এক্ষেত্রে 1 GB ডেটা সর্ট করতে হবে কিন্তু প্রধান মেমরি আছে মাত্র 100 MB। তাই এমন একটি সর্টিং কৌশল প্রয়োজন যা মেমরির সীমাবদ্ধতা মোকাবেলা করতে পারে।

সঠিক উত্তর হলো Merge Sort।

Merge Sort (মার্জ সর্ট) কেন সবচেয়ে উপযুক্ত:

    
• মার্জ সর্ট একটি 'Divide and Conquer' (ডিভাইড অ্যান্ড কনকার) অ্যালগরিদম। এটি ডেটাকে ছোট ছোট অংশে বিভক্ত করে (যা RAM এ ফিট হতে পারে), প্রতিটি অংশকে আলাদাভাবে সর্ট করে এবং তারপর সর্ট করা অংশগুলোকে একত্রিত (merge) করে।
    
• এক্সটার্নাল সর্টিং এর জন্য মার্জ সর্ট সবচেয়ে উপযোগী কারণ এটি ডেটাকে 'runs' (রান) বা ছোট ছোট ব্লক (block) এ ভাগ করে। প্রতিটি রানকে মেমরিতে আনা হয়, সর্ট করা হয় (যেমন ইন-মেমরি সর্ট অ্যালগরিদম ব্যবহার করে), এবং ডিস্কে লেখা হয়।
    
• এরপর, এই সর্ট করা রানগুলোকে একের পর এক মার্জ করে চূড়ান্ত সর্ট করা ডেটা তৈরি করা হয়। এই প্রক্রিয়ায়, একবারে কেবলমাত্র অল্প সংখ্যক রান মেমরিতে লোড করা হয় মার্জ করার জন্য। এটি প্রধান মেমরির সীমাবদ্ধতা থাকা সত্ত্বেও বিশাল ডেটাসেট পরিচালনা করতে পারে।
    
• এর টাইম কমপ্লেক্সিটি O(n log n) যা বড় ডেটাসেটের জন্য বেশ কার্যকর।

অন্যান্য অপশনগুলো কেন অনুপযুক্ত:

    
• Heap Sort (হিপ সর্ট): এটি একটি ইন-প্লেস সর্টিং অ্যালগরিদম (in-place sorting algorithm) যা কার্যকরীভাবে কাজ করার জন্য সমস্ত ডেটা প্রধান মেমরিতে থাকার উপর নির্ভর করে। এটি হিপ ডেটা স্ট্রাকচার (heap data structure) তৈরি করে যা বড় ডেটার জন্য RAM এর বাইরে কার্যকর নয়।
    
• Quick Sort (কুইক সর্ট): এটিও একটি ইন-প্লেস সর্টিং অ্যালগরিদম এবং এটি সাধারণত তার কার্যকারিতার জন্য ডেটা প্রধান মেমরিতে থাকার উপর নির্ভর করে। এর রিকার্সিভ (recursive) প্রকৃতি এবং পার্টিশন (partition) মেকানিজম এক্সটার্নাল সর্টিং এর জন্য উপযুক্ত নয় কারণ এটি ঘন ঘন ডিস্ক অ্যাক্সেসের (disk access) দিকে পরিচালিত করবে, যা অত্যন্ত ধীর।
    
• Insertion Sort (ইনসারশন সর্ট): এটি একটি খুব ধীর অ্যালগরিদম (টাইম কমপ্লেক্সিটি O(n^2)) যা ছোট ডেটাসেটের জন্য উপযুক্ত। বিশাল ডেটাসেটের জন্য এটি একেবারেই অদক্ষ এবং এক্সটার্নাল সর্টিং এর জন্য উপযুক্ত নয়।

অতএব, প্রধান মেমরির সীমাবদ্ধতা থাকা সত্ত্বেও 1 GB ডেটা সর্ট করার জন্য Merge Sort হলো সবচেয়ে উপযুক্ত এবং কার্যকর কৌশল।